/*
 class Solution {
public:
    void reverseString(vector<char>& s) 
    {
        size_t begin = 0;
        size_t end = s.size()-1;
        while(begin<end)
        {

            swap(s[begin],s[end]);
            --end；
            ++begin；
        }

    }
};*/

/*class Solution {
public:
    int firstUniqChar(string s) 
    {
     int count[26]={0};
     for(auto e : s)
     {
         ++count[e -'a'];
     }
     for(size_t i=0;i<s.size();i++)
       {
           if(count[s[i]-'a']==1)
           {

//超时
//  int firstUniqChar(string s) 
//     {
     
//         size_t begin = 0;
//         size_t end = s.size()-1;
//         while(begin < end)
//         {
//             int cur = begin+1;
//             while(cur <= end)
//             {
//                 if(s[cur] != s[begin] )
//                 {
//                     cur++;
//                     if(cur == end)
//                     {
//                         return begin;
//                     }
//                 } 
//             }
//            ++begin;
//         }
//         return -1;
//     }*/
class Solution {
  public:

    bool isnumber(char a) {
        //是数字返回真，不是数字返回假
        if ((a >= '0' && a <= '9') || (a == '+' || a == '-'))
            return true;
        return false;
    }

    int StrToInt(string str) {
        int count = 0;
        int val = 0;
        int begin = 0;
        int end = str.size()-1;
        string::iterator it = str.end()-1;
        while (end >= begin) {

            //不是数字/+/-就返回0
            if (!isnumber(*it)) {
                return 0;
            }

            //是+/-，减次方数
            if (*it == '+' || *it == '-')
            {
                if(*it == '-')
                {
                    val=-val;
                }
            }
            else  
            {
                 val += (*it - '0') * pow(10, count);
                 count++;  
            }   
            --it;
            end--;
        }
        return val;
    }
};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA=1,lenB=1;
        struct ListNode *curA=headA,*curB=headB;

        while(curA->next)
        {
            curA=curA->next;
            ++lenA;
        }
        while(curB->next)
        {
            curB=curB->next;
            ++lenB;
        }
        //尾节点不相等，无交点
        if(curA!=curB)
        {
            return NULL;
        }

        int gap=abs(lenA-lenB);
        struct ListNode * longlen=headA, *shortlen=headB;
        if(lenA<lenB)
        {
            longlen=headB;
            shortlen=headA;
        }
        while(gap--)
        {
            longlen=longlen->next;
        }
         while(shortlen != longlen)
        {
            longlen=longlen->next;
            shortlen=shortlen->next;
        }
        return shortlen;


    }

    // ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    //     while(headA!=nullptr)
    //     {
    //         //每次内层结束都重置cur
    //         ListNode *cur = headB;
    //         while(cur!=nullptr)
    //         {
                    ////比较地址而不是值
    //             if(headA==cur)
    //             {
    //                 return headA;
    //             }
    //             cur=cur->next;
    //         }

    //         headA=headA->next;
    //     }
    //     return NULL;
    // }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        struct ListNode* slow=head,*fast=head;
        while(fast && fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)
            {
                return true;
            }
        }
        return false;;
        
    }
};
